// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssagen

import (
	"container/heap"
	"fmt"

	"cmd/compile/internal/ir"
	"cmd/compile/internal/ssa"
	"cmd/compile/internal/types"
	"cmd/internal/src"
)

// 此文件包含在函数中放置phi节点的算法。
// 对于小函数，我们使用Braun、Buchwald、Hack、Leißa、Mallon和Zwinkau。
// https:
// 对于大型函数，我们使用Sreedhar&Gao：放置Φ-节点的线性时间算法。
// http:

const smallBlocks = 500

const debugPhi = false

// fwdRefAux包装了一个任意的ir。节点作为ssa。Aux用于OpFwdref。
type fwdRefAux struct {
	_ [0]func() // 确保ir。不比较节点是否相等
	N ir.Node
}

func (fwdRefAux) CanBeAnSSAAux() {}

// insertPhis在函数中查找phi为
// 必需的所有位置并插入它们。
// 使用FwdRef ops查找变量的所有用法，使用s.defvars查找
// 所有定义。
// 插入Phi值，并将所有FWDREF更改为相应Phi或定义的副本
// 。
// TODO:以某种方式将此部分作为cmd/compile/internal/ssa的一部分？
func (s *state) insertPhis() {
	if len(s.f.Blocks) <= smallBlocks {
		sps := simplePhiState{s: s, f: s.f, defvars: s.defvars}
		sps.insertPhis()
		return
	}
	ps := phiState{s: s, f: s.f, defvars: s.defvars}
	ps.insertPhis()
}

type phiState struct {
	s       *state                   // SSA state 
	f       *ssa.Func                // 处理
	defvars []map[ir.Node]*ssa.Value // 每个块末尾定义的变量

	varnum map[ir.Node]int32 // 变量编号

	// 支配树属性
	idom  []*ssa.Block // 支配父
	tree  []domBlock   // 支配子+兄弟
	level []int32      // 支配树中的级别（0=根目录或不可访问，1=根目录的子目录，…）

	// 暂存位置
	priq   blockHeap    // 块的优先级队列，更高级别（朝向叶子）=更高优先级
	q      []*ssa.Block // 内部循环队列
	queued *sparseSet   // 已放入q 
	hasPhi *sparseSet   // 具有phi 
	hasDef *sparseSet   // 具有我们正在处理的变量

	// 杂项
	placeholder *ssa.Value // 值，用作“尚未设置”占位符。
}

func (s *phiState) insertPhis() {
	if debugPhi {
		fmt.Println(s.f.String())
	}

	// 找到我们需要匹配读写操作的所有变量。
	// 此步骤将删除任何基本的仅限块的变量。
	// 为这些变量生成编号。
	s.varnum = map[ir.Node]int32{}
	var vars []ir.Node
	var vartypes []*types.Type
	for _, b := range s.f.Blocks {
		for _, v := range b.Values {
			if v.Op != ssa.OpFwdRef {
				continue
			}
			var_ := v.Aux.(fwdRefAux).N

			// 优化：查看1个块中的定义。
			if len(b.Preds) == 1 {
				c := b.Preds[0].Block()
				if w := s.defvars[c.ID][var_]; w != nil {
					v.Op = ssa.OpCopy
					v.Aux = nil
					v.AddArg(w)
					continue
				}
			}

			if _, ok := s.varnum[var_]; ok {
				continue
			}
			s.varnum[var_] = int32(len(vartypes))
			if debugPhi {
				fmt.Printf("var%d = %v\n", len(vartypes), var_)
			}
			vars = append(vars, var_)
			vartypes = append(vartypes, v.Type)
		}
	}

	if len(vartypes) == 0 {
		return
	}

	// 找到我们需要处理的变量的所有定义。
	// defs[n]包含分配了变量号n的所有块。
	defs := make([][]*ssa.Block, len(vartypes))
	for _, b := range s.f.Blocks {
		for var_ := range s.defvars[b.ID] { // TODO:以其他方式编码DEFVAR（显式操作）？使defvars[n]成为一个切片而不是一张地图。
			if n, ok := s.varnum[var_]; ok {
				defs[n] = append(defs[n], b)
			}
		}
	}

	// 生成支配树。
	s.idom = s.f.Idom()
	s.tree = make([]domBlock, s.f.NumBlocks())
	for _, b := range s.f.Blocks {
		p := s.idom[b.ID]
		if p != nil {
			s.tree[b.ID].sibling = s.tree[p.ID].firstChild
			s.tree[p.ID].firstChild = b
		}
	}
	// 计算支配树中的级别。
	// 使用父指针，我们可以在没有任何辅助存储的情况下进行深度优先行走。
	s.level = make([]int32, s.f.NumBlocks())
	b := s.f.Entry
levels:
	for {
		if p := s.idom[b.ID]; p != nil {
			s.level[b.ID] = s.level[p.ID] + 1
			if debugPhi {
				fmt.Printf("level %s = %d\n", b, s.level[b.ID])
			}
		}
		if c := s.tree[b.ID].firstChild; c != nil {
			b = c
			continue
		}
		for {
			if c := s.tree[b.ID].sibling; c != nil {
				b = c
				continue levels
			}
			b = s.idom[b.ID]
			if b == nil {
				break levels
			}
		}
	}

	// 分配临时位置。
	s.priq.level = s.level
	s.q = make([]*ssa.Block, 0, s.f.NumBlocks())
	s.queued = newSparseSet(s.f.NumBlocks())
	s.hasPhi = newSparseSet(s.f.NumBlocks())
	s.hasDef = newSparseSet(s.f.NumBlocks())
	s.placeholder = s.s.entryNewValue0(ssa.OpUnknown, types.TypeInvalid)

	// 为每个变量生成phi运算。
	for n := range vartypes {
		s.insertVarPhis(n, vars[n], defs[n], vartypes[n])
	}

	// 将FwdRefs解析为正确的写入或phi。
	s.resolveFwdRefs()

	// 清除phi ops的生长素字段中存储的变量数。他们不再需要了。
	for _, b := range s.f.Blocks {
		for _, v := range b.Values {
			if v.Op == ssa.OpPhi {
				v.AuxInt = 0
			}
			// 任何剩余的FWDREF都是死代码。
			if v.Op == ssa.OpFwdRef {
				v.Op = ssa.OpUnknown
				v.Aux = nil
			}
		}
	}
}

func (s *phiState) insertVarPhis(n int, var_ ir.Node, defs []*ssa.Block, typ *types.Type) {
	priq := &s.priq
	q := s.q
	queued := s.queued
	queued.clear()
	hasPhi := s.hasPhi
	hasPhi.clear()
	hasDef := s.hasDef
	hasDef.clear()

	// 将定义块添加到优先级队列。
	for _, b := range defs {
		priq.a = append(priq.a, b)
		hasDef.add(b.ID)
		if debugPhi {
			fmt.Printf("def of var%d in %s\n", n, b)
		}
	}
	heap.Init(priq)

	// 访问定义变量n的区块，从最深到最浅。
	for len(priq.a) > 0 {
		currentRoot := heap.Pop(priq).(*ssa.Block)
		if debugPhi {
			fmt.Printf("currentRoot %s\n", currentRoot)
		}
		// 在定义下面行走子树。
		// 跳过我们在以前的迭代中完成的子树。
		// 找到由定义支配的树的边（支配边界）。
		// 在目标区块插入PHI。
		if queued.contains(currentRoot.ID) {
			s.s.Fatalf("root already in queue")
		}
		q = append(q, currentRoot)
		queued.add(currentRoot.ID)
		for len(q) > 0 {
			b := q[len(q)-1]
			q = q[:len(q)-1]
			if debugPhi {
				fmt.Printf("  processing %s\n", b)
			}

			currentRootLevel := s.level[currentRoot.ID]
			for _, e := range b.Succs {
				c := e.Block()
				// TODO:如果变量在c处无效，请跳过它。
				if s.level[c.ID] > currentRootLevel {
					// 一条D边，或目标位于currentRoot子树中的边。
					continue
				}
				if hasPhi.contains(c.ID) {
					continue
				}
				// 为变量n在c区添加一个phi。
				hasPhi.add(c.ID)
				v := c.NewValue0I(currentRoot.Pos, ssa.OpPhi, typ, int64(n)) // TODO:行号对吗？
				// 注意：我们将变量号存储在phi的生长素字段中。phi building暂时使用。
				if var_.Op() == ir.ONAME {
					s.s.addNamedValue(var_.(*ir.Name), v)
				}
				for range c.Preds {
					v.AddArg(s.placeholder) // 实际参数将由resolveFwdRefs填写。
				}
				if debugPhi {
					fmt.Printf("new phi for var%d in %s: %s\n", n, c, v)
				}
				if !hasDef.contains(c.ID) {
					// 现在在c区有了这个变量的新定义。
					// 将其添加到优先级队列中进行探索。
					heap.Push(priq, c)
					hasDef.add(c.ID)
				}
			}

			// 如果孩子还没有被探视，就去探望他们。
			for c := s.tree[b.ID].firstChild; c != nil; c = s.tree[c.ID].sibling {
				if !queued.contains(c.ID) {
					q = append(q, c)
					queued.add(c.ID)
				}
			}
		}
	}
}

// resolveFwdRefs将所有FwdRef使用的链接链接到其最接近的主要定义。
func (s *phiState) resolveFwdRefs() {
	// 对支配树进行深度优先遍历，跟踪每个变量最近看到的值。

	// 在行走的当前点将变量ID映射到SSA值。
	values := make([]*ssa.Value, len(s.varnum))
	for i := range values {
		values[i] = s.placeholder
	}

	// 有一大堆工作要做。
	type stackEntry struct {
		b *ssa.Block // 块浏览

		// 变量/值对退出时恢复
		n int32 // 变量ID 
		v *ssa.Value

		// 注意：只设置b或n，v中的一个。
	}
	var stk []stackEntry

	stk = append(stk, stackEntry{b: s.f.Entry})
	for len(stk) > 0 {
		work := stk[len(stk)-1]
		stk = stk[:len(stk)-1]

		b := work.b
		if b == nil {
			// 从块中退出时，此案例将撤消以下所做的任何分配。
			values[work.n] = work.v
			continue
		}

		// 将PHI处理为新的DEF。他们在这个街区走在前头。
		for _, v := range b.Values {
			if v.Op != ssa.OpPhi {
				continue
			}
			n := int32(v.AuxInt)
			// 记住旧的分配，这样我们可以在退出b时撤消它。
			stk = append(stk, stackEntry{n: n, v: values[n]})
			// 记录新的分配。
			values[n] = v
		}

		// 将FwdRef op替换为其变量的当前传入值。
		for _, v := range b.Values {
			if v.Op != ssa.OpFwdRef {
				continue
			}
			n := s.varnum[v.Aux.(fwdRefAux).N]
			v.Op = ssa.OpCopy
			v.Aux = nil
			v.AddArg(values[n])
		}

		// 为b中定义的变量建立值。
		for var_, v := range s.defvars[b.ID] {
			n, ok := s.varnum[var_]
			if !ok {
				// 某些变量不存在于基本块边界上。
				continue
			}
			// 记住旧的作业，这样我们可以在退出b时撤消它。
			stk = append(stk, stackEntry{n: n, v: values[n]})
			// 记录新的作业。
			values[n] = v
		}

		// 用当前传入值替换后续的phi args。
		for _, e := range b.Succs {
			c, i := e.Block(), e.Index()
			for j := len(c.Values) - 1; j >= 0; j-- {
				v := c.Values[j]
				if v.Op != ssa.OpPhi {
					break // 在phi建设期间，所有phi将位于街区的尽头。
				}
				// 仅设置已解析的参数。
				// 对于非常宽的CFG，这将显著加快phi分辨率。
				// 见戈朗。org/issue/8225。
				if w := values[v.AuxInt]; w.Op != ssa.OpUnknown {
					v.SetArg(i, w)
				}
			}
		}

		// 让孩子们在支配树中行走。
		for c := s.tree[b.ID].firstChild; c != nil; c = s.tree[c.ID].sibling {
			stk = append(stk, stackEntry{b: c})
		}
	}
}

// domBlock包含额外的每个块信息，用于记录支配树。
type domBlock struct {
	firstChild *ssa.Block // 控制树中块的第一个子
	sibling    *ssa.Block // 控制树中父级的下一个子
}

// 块堆用作优先级队列，以实现Sreedhar和Gao的PiggyBank 
// 。这篇论文使用了一个数组，这个数组渐近地比
// 更好，但在通常情况下，当小猪桶
// 包含一组稀疏的块时，它的性能更差。
type blockHeap struct {
	a     []*ssa.Block // 堆中的块ID 
	level []int32      // 控制树中的深度（静态，用于确定优先级）
}

func (h *blockHeap) Len() int      { return len(h.a) }
func (h *blockHeap) Swap(i, j int) { a := h.a; a[i], a[j] = a[j], a[i] }

func (h *blockHeap) Push(x interface{}) {
	v := x.(*ssa.Block)
	h.a = append(h.a, v)
}
func (h *blockHeap) Pop() interface{} {
	old := h.a
	n := len(old)
	x := old[n-1]
	h.a = old[:n-1]
	return x
}
func (h *blockHeap) Less(i, j int) bool {
	return h.level[h.a[i].ID] > h.level[h.a[j].ID]
}

// TODO:当
// 变量已死亡时，停止遍历迭代的控制边界。也许可以通过检查我们所在的
// 节点是否由所有读取操作反向控制来检测？
// 在所有阅读中，由最高共同继承人主导的反向阅读？

// 副本/ssa/sparseset。转到
// TODO:将此文件移动到/ssa，然后在那里使用sparseSet。
type sparseSet struct {
	dense  []ssa.ID
	sparse []int32
}

// newSparseSet返回一个稀疏集，该稀疏集可以表示0到n-1之间的整数
// 用于小函数的变量。
func newSparseSet(n int) *sparseSet {
	return &sparseSet{dense: nil, sparse: make([]int32, n)}
}

func (s *sparseSet) contains(x ssa.ID) bool {
	i := s.sparse[x]
	return i < int32(len(s.dense)) && s.dense[i] == x
}

func (s *sparseSet) add(x ssa.ID) {
	i := s.sparse[x]
	if i < int32(len(s.dense)) && s.dense[i] == x {
		return
	}
	s.dense = append(s.dense, x)
	s.sparse[x] = int32(len(s.dense)) - 1
}

func (s *sparseSet) clear() {
	s.dense = s.dense[:0]
}

type simplePhiState struct {
	s         *state                   // SSA state 
	f         *ssa.Func                // 处理
	fwdrefs   []*ssa.Value             // 要处理的FwdRef列表
	defvars   []map[ir.Node]*ssa.Value // 每个块末尾定义的变量
	reachable []bool                   // 哪些块可以访问
}

func (s *simplePhiState) insertPhis() {
	s.reachable = ssa.ReachableBlocks(s.f)

	// 查找FwdRef ops。
	for _, b := range s.f.Blocks {
		for _, v := range b.Values {
			if v.Op != ssa.OpFwdRef {
				continue
			}
			s.fwdrefs = append(s.fwdrefs, v)
			var_ := v.Aux.(fwdRefAux).N
			if _, ok := s.defvars[b.ID][var_]; !ok {
				s.defvars[b.ID][var_] = v // 将FwdDefs视为定义。
			}
		}
	}

	var args []*ssa.Value

loop:
	for len(s.fwdrefs) > 0 {
		v := s.fwdrefs[len(s.fwdrefs)-1]
		s.fwdrefs = s.fwdrefs[:len(s.fwdrefs)-1]
		b := v.Block
		var_ := v.Aux.(fwdRefAux).N
		if b == s.f.Entry {
			// 输入时不应存在任何变量。这个街区死了。
			s.s.Fatalf("Value live at entry. It shouldn't be. func %s, node %v, value %v", s.f.Name, var_, v)
		}
		if !s.reachable[b.ID] {
			// 只要格式正确，我们在这里使用什么并不重要。
			v.Op = ssa.OpUnknown
			v.Aux = nil
			continue
		}
		// 查找每个前置变量的变量值。决定我们是否需要phi。如果
		args = args[:0]
		for _, e := range b.Preds {
			args = append(args, s.lookupVarOutgoing(e.Block(), v.Type, var_, v.Pos))
		}

		// 有两个不同的参数（都不是v），我们需要一个phi。
		var w *ssa.Value
		for _, a := range args {
			if a == v {
				continue // 自引用
			}
			if a == w {
				continue // 已经有此见证
			}
			if w != nil {
				// 两个见证人，需要phi值
				v.Op = ssa.OpPhi
				v.AddArgs(args...)
				v.Aux = nil
				continue loop
			}
			w = a // 保存见证
		}
		if w == nil {
			s.s.Fatalf("no witness for reachable phi %s", v)
		}
		// 一个见证人。使v成为w的副本。
		v.Op = ssa.OpCopy
		v.Aux = nil
		v.AddArg(w)
	}
}

// lookupVarOutgoing在块b的末尾找到变量的值。
func (s *simplePhiState) lookupVarOutgoing(b *ssa.Block, t *types.Type, var_ ir.Node, line src.XPos) *ssa.Value {
	for {
		if v := s.defvars[b.ID][var_]; v != nil {
			return v
		}
		// 变量不是由b定义的，我们还没有查找它。
		// 如果b正好有一个前导，循环在那里查找它。
		// 否则，请放弃并插入一个新的FwdRef，稍后再解决。
		if len(b.Preds) != 1 {
			break
		}
		b = b.Preds[0].Block()
		if !s.reachable[b.ID] {
			// 这是罕见的；这种情况发生在死代码中奇怪地交错的无限循环中。
			// 见第19783期。
			break
		}
	}
	// 为变量生成一个FwdRef并返回该值。
	v := b.NewValue0A(line, ssa.OpFwdRef, t, fwdRefAux{N: var_})
	s.defvars[b.ID][var_] = v
	if var_.Op() == ir.ONAME {
		s.s.addNamedValue(var_.(*ir.Name), v)
	}
	s.fwdrefs = append(s.fwdrefs, v)
	return v
}
